package com.leecode;


public class Leet55 {
	public static void main(String[] args) {
//		new Leet55().canJump(new int[]{1, 0, 1, 0});
		new Leet55().canJump2(new int[]{2,3,1,1,4});
	}
	public boolean canJump(int[] nums) {
		if(nums.length==1)return true;
		if(nums[0]==0)return false;

		return recur(nums,nums.length-1);
	}
	//思路::前到后,,可以但超时
	// public boolean recur(int[] nums,int moveB,int length){
	//     if(nums[moveB]>=length-1)return true;
	//     if(nums[moveB]==0)return false;
	//     for(int a=1;a<=nums[moveB];a++){
	//         if(recur(nums,moveB+a,length-a)){
	//             return true;
	//         }
	//     }

	//     return false;
	// }

	public boolean recur(int[] nums,int lastIndex){
		if(lastIndex==0)return true;

		for(int a=lastIndex-1;a>=0;a--){
			if(nums[a]<lastIndex-a){
				continue;
			}else{
				if(a==0)return true;
				if(recur(nums,a)){
					return true;
				}
			}
		}
		return false;
	}

	/**
	 * 81%,5%,自己想出来的,用到了类似dp的数组,但自己觉得绝对和dp没关系!!
	 * 110301?  len==7
	 * 0123456  idx
	 * 122646?  idx[0,5]我只关心有没有>=原数组最后一位的idx,也就是说只关心有没有>=6的,最靠近?的idx有5,3,
	 * 原问题"能否跳到idx6"问题转化为
	 * "能否跳到idx5"
	 * "能否跳到idx3",这两个问题有一定的关联,我都能跳到idx5了,必定能跳到idx3,所以这里可以优化A,但实际是递归少的反而负优化?!!!!!!!!!!!!!
	 *
	 * 110300?  len==7
	 * 0123456  idx
	 * 122645?  idx[0,5]我只关心有没有>=原数组最后一位的idx,也就是说只关心有没有>=6的,最靠近?的idx只有3,原问题"能否跳到idx6"问题转化为"能否跳到idx3"
	 */
	public boolean canJump2(int[] nums) {
		int[] res=new int[nums.length];

		for(int a=0;a<nums.length;a++){
			res[a]=a+nums[a];
		}

		return recur2(res,res.length-1);
	}
	public boolean recur2(int[] res,int idx){
		if(idx==0)return true;

		for(int a=idx-1;a>=0;a--){//优化A
//		for(int a=0;a<=idx-1;a++){//优化A
			if(res[a]>=idx){
				return recur2(res,a);
			}
		}
		return false;
	}
}
